#include <iostream>

template<class K>
struct BSTNode
{
    explicit BSTNode(const K& key = K())
        : _left(nullptr)
        , _right(nullptr)
        , _key(key)
    {}

    BSTNode<K>* _left;
    BSTNode<K>* _right;
    K _key;
};

template<class K>
class BSTree
{
    typedef BSTNode<K> Node;
public:
    BSTree()
        : _root(nullptr)
    {}

    BSTree(const BSTree<K>& t)
    {
        _root = Copy(t._root);
    }
    Node* Copy(Node* root)
    {
        if(root == nullptr)
            return nullptr;
        Node* newNode = new Node(root->_key);
        newNode->_left = Copy(root->_left);
        newNode->_right = Copy(root->_right);
        return newNode;
    }

    BSTree<K>& operator=(BSTree<K> t)
    {
        std::swap(_root, t._root);
        return *this;
    }

    ~BSTree()
    {
        Destory(_root);
    }
    void Destory(Node*& root)
    {
        if(root == nullptr)
            return;
        Destory(root->_left);
        Destory(root->_right);
        delete root;
        root = nullptr;
    }

    bool InsertR(const K& key)
    {
        return _InsertR(_root, key);
    }

    bool EraseR(const K& key)
    {
        return _EraseR(_root, key);
    }

    void InOrder()
    {}

    bool FindR(const K& key)
    {
        return _FindR(_root, key);
    }

private:
    bool _FindR(Node* root, const K& key)
    {
        if(root == nullptr)
            return false;
        if(key < root->_key)
            return _FindR(root->_left, key);
        else if(key > root->_key)
            return _FindR(root->_right, key);
        else
            return true;
    }

    bool _InsertR(Node*& root, const K& key)
    {
        if(root == nullptr)
        {
            root = new Node(key);
            return true;
        }

        if(key < root->_key)
            return _InsertR(root->_left, key);
        else if(key > root->_key)
            return _InsertR(root->_right, key);
        else
            return false;
    }

    bool _EraseR(Node*& root, const K& key)
    {
        if(root == nullptr)
            return false;

        if(key < root->_key)
            return _EraseR(root->_left, key);
        else if(key > root->_key)
            return _EraseR(root->_right, key);
        else
        {
            Node* del = root;
            //1.left == nullptr
            //2.right == nullptr
            //3.left != nullptr && right != nullptr
            if(root->_left == nullptr)
                root = root->_right;
            else if(root->_right == nullptr)
                root = root->_left;
            else
            {
                Node* leftMax = root->_left;
                while(leftMax->_right != nullptr)
                {
                    leftMax = leftMax->_right;
                }
                std::swap(leftMax->_key, root->_key);
                return _EraseR(root->_left, key);
            }
            delete del;
            return true;
        }
    }

    Node* _root;
};

int main()
{
    return 0;
}